/*********************************************************************************
 *      Copyright:  (C) 2017 luminqi
 *                  All rights reserved.
 *
 *       Filename:  fast_sort.c
 *    Description:  This file 
 *                 
 *        Version:  1.0.0(2017年08月26日)
 *         Author:  luminqi <958822582@qq.com>
 *      ChangeLog:  1, Release initial version on "2017年08月26日 00时42分42秒"
 *                 
 ********************************************************************************/
#include <stdio.h>

void fast_sort(int a[], int left, int right);
int main(int argc, char **argv)
{
    int a[9] = {4,5,6,7,8,9,1,2,3};
    int i = 0;

    printf("before sort:\n");
    for (i=0; i<9; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");

    fast_sort(a, 0, 8);
    printf("after sort:\n");
    for (i=0;i<9;i++)
    {
        printf("%d ",a[i]);
    }

    printf("\n");
    return 0;
}

void fast_sort(int a[], int left, int right)
{
    int i = left;
    int j = right;
    int key = a[left];
    
    if(left >= right)
    {
        return;
    }

    while (i < j)
    {
        while((i < j)&&(key <= a[j]))
        {
            j--;
        }
        a[i] = a[j];
        while((i < j)&&(key >= a[i]))
        {
            i++;
        }
        a[j] = a[i];
    }
    a[i] = key;
    fast_sort(a, left, i-1);
    fast_sort(a, i+1, right);
    
    return;

}
